//https://leetcode.cn/problems/minimum-window-substring/submissions/502838356/?envType=study-plan-v2&envId=top-100-liked
//滑动窗口思想；

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    unordered_map<char, int>  smap,tmap;
    bool check(){
        for(auto item : tmap){
            if(smap.find(item.first) == smap.end()){
                return false;
            }
            if(smap[item.first] < tmap[item.first]) {
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        
        for (auto item : t) {
            ++tmap[item];
        }
        std::string res;
        for (int i = 0, j = 0; i < s.size(); i ++) {
            ++smap[s[i]];

            while(tmap.find(s[j]) != tmap.end() && smap[s[j]] >tmap[s[j]]) {
               --smap[s[j]];
               if(smap[s[j]] == 0){
                    smap.erase(s[j]);
                }
               ++j;
            }
            
            while(check()){
                if(res.empty()||i - j + 1 < res.size()) {
                    res=s.substr(j,i-j+1);
                }
                // std::cout<<"----------"<<std::endl;
                // std::cout<<"cur_str:"<<s.substr(j,i-j+1)<<std::endl;
                // std::cout<<"res:"<<res <<",t:"<< t<<std::endl;
                // std::cout<<"j:"<<j << ",i:"<<i<<std::endl;
                
                --smap[s[j]];
                if(smap[s[j]] == 0){
                    smap.erase(s[j]);
                }
                ++j;
            }
        }
        return res;
    }
};